package Other;

public class leet_746 {
    public static void main(String[] args) {
        Solution_746 p = new Solution_746();

        // int[] cost = new int[]{10, 15, 20};

        int[] cost = new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

        int value = p.minCostClimbingStairs(cost);
        System.out.println(value);
    }

}


class Solution_746 {
    public int minCostClimbingStairs(int[] cost) {
        if(cost.length==1){
            // 直接选择2步到顶层
            return 0;
        }else if(cost.length==2){
            // 2层就选小的开始
            return  Math.min(cost[0], cost[1]);
        }
        // 开始使用动态回归
        int[] dp = new int[cost.length + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i=2; i<cost.length; i++){
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }
        // 由于登顶时cost的数组下标不完全所以特殊处理
        dp[cost.length] = Math.min(dp[cost.length-1], dp[cost.length-2]);
        return dp[cost.length];
    }
}